package MiddlePractice;

import org.junit.Test;

public class Demo240 {
//	240. 搜索二维矩阵 II
//	编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
//
//	每行的元素从左到右升序排列。
//	每列的元素从上到下升序排列。
	
	public boolean searchMatrix(int[][] matrix, int target) {
		for(int[] num : matrix) {
			if(halfSearch(num, target)) {
				return true;
			}
		}
		return false;
    }
	
	private boolean halfSearch(int[] nums, int target) {
		
		int left = 0, right = nums.length-1;
		
		while(left <= right) {
			int mid = (right + left) / 2;
			if(nums[mid] == target) {
				return true;
			}
			else if(nums[mid] > target) {
				right = mid-1;
			}
			else {
				left = mid+1;
			}
		}
		return false;
	}

	@Test
	public void test_240() {
		int[] nums = {1,2,3,5,6,7,8,9,13,16};
		System.out.println(halfSearch(nums, 16));
	}
	
}
